Search Results

Documents authored by Grilo, Alex B.

Document
DOI: 10.4230/LIPIcs.ITC.2023.9
Quantum Security of Subset Cover Problems

Authors: Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
The subset cover problem for k ≥ 1 hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, ...). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make Ω((k+1)^{-(2^k)/(2^{k+1}-1})⋅ N^{(2^{k}-1})/(2^{k+1}-1)}) queries to the underlying hash functions with codomain size N to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general (r,k)-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a r-chosen message attack (for r ≥ 1). We prove that a generic quantum algorithm needs to make Ω(N^{k/5}) queries to the underlying hash functions to find a (1,k)-subset cover. We also propose a quantum algorithm that finds a (r,k)-subset cover making O (N^{k/(2+2r)}) queries to the k hash functions.
Cite as

Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud. Quantum Security of Subset Cover Problems. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bouazizermann_et_al:LIPIcs.ITC.2023.9,
  author =	{Bouaziz-Ermann, Samuel and Grilo, Alex B. and Vergnaud, Damien},
  title =	{{Quantum Security of Subset Cover Problems}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.9},
  URN =		{urn:nbn:de:0030-drops-183378},
  doi =		{10.4230/LIPIcs.ITC.2023.9},
  annote =	{Keywords: Cryptography, Random oracle model, Quantum information}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.36
Two Combinatorial MA-Complete Problems

Authors: Dorit Aharonov and Alex B. Grilo

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Despite the interest in the complexity class MA, the randomized analog of NP, there are just a few known natural (promise-)MA-complete problems. The first such problem was found by Bravyi and Terhal (SIAM Journal of Computing 2009); this result was then followed by Crosson, Bacon and Brown (PRE 2010) and then by Bravyi (Quantum Information and Computation 2015). Surprisingly, each of these problems is either from or inspired by quantum computation. This fact makes it hard for classical complexity theorists to study these problems, and prevents potential progress, e.g., on the important question of derandomizing MA. In this note we define two new natural combinatorial problems and we prove their MA-completeness. The first problem, that we call approximately-clean approximate-connected-component (ACAC), gets as input a succinctly described graph, some of whose vertices are marked. The problem is to decide whether there is a connected component whose vertices are all unmarked, or the graph is far from having this property. The second problem, called SetCSP, generalizes in a novel way the standard constraint satisfaction problem (CSP) into constraints involving sets of strings. Technically, our proof that SetCSP is MA-complete is a fleshing out of an observation made in (Aharonov and Grilo, FOCS 2019), where it was noted that a restricted case of Bravyi and Terhal’s MA complete problem (namely, the uniform case) is already MA complete; and, moreover, that this restricted case can be stated using classical, combinatorial language. The fact that the first, arguably more natural, problem of ACAC is MA-hard follows quite naturally from this proof as well; while containment of ACAC in MA is simple, based on the theory of random walks. We notice that this work, along with a translation of the main result of Aharonov and Grilo to the SetCSP problem, implies that finding a gap-amplification procedure for SetCSP (in the spirit of the gap-amplification procedure introduced in Dinur’s PCP proof) would imply MA=NP. In fact, the problem of finding gap-amplification for SetCSP is equivalent to the MA=NP problem. This provides an alternative new path towards the major problem of derandomizing MA. Deriving a similar statement regarding gap amplification of a natural restriction of $ACAC$ remains an open question.
Cite as

Dorit Aharonov and Alex B. Grilo. Two Combinatorial MA-Complete Problems. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aharonov_et_al:LIPIcs.ITCS.2021.36,
  author =	{Aharonov, Dorit and Grilo, Alex B.},
  title =	{{Two Combinatorial MA-Complete Problems}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.36},
  URN =		{urn:nbn:de:0030-drops-135754},
  doi =		{10.4230/LIPIcs.ITCS.2021.36},
  annote =	{Keywords: Merlin-Arthur proof systems, Constraint sastifation problem, Random walks}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.28
A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round

Authors: Alex B. Grilo

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers in multiple rounds of communication. In this work, we propose the first protocol where the client delegates her quantum computation to two servers in one-round of communication. Another advantage of our protocol is that it is conceptually simpler than previous protocols. The parameters of our protocol also make it possible to prove security even if the servers are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light, making it the first relativistic protocol for quantum computation.
Cite as

Alex B. Grilo. A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grilo:LIPIcs.ICALP.2019.28,
  author =	{Grilo, Alex B.},
  title =	{{A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.28},
  URN =		{urn:nbn:de:0030-drops-106044},
  doi =		{10.4230/LIPIcs.ICALP.2019.28},
  annote =	{Keywords: quantum computation, quantum cryptography, delegation of quantum computation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.21
Pointer Quantum PCPs and Multi-Prover Games

Authors: Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. Our new conjecture is weaker than the original QPCP conjecture and hence provides a natural intermediate step towards proving the quantum PCP theorem. Furthermore, this is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.
Cite as

Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi. Pointer Quantum PCPs and Multi-Prover Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grilo_et_al:LIPIcs.MFCS.2016.21,
  author =	{Grilo, Alex B. and Kerenidis, Iordanis and Pereszl\'{e}nyi, Attila},
  title =	{{Pointer Quantum PCPs and Multi-Prover Games}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.21},
  URN =		{urn:nbn:de:0030-drops-64364},
  doi =		{10.4230/LIPIcs.MFCS.2016.21},
  annote =	{Keywords: computational complexity, quantum computation, PCP theorem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact